
public class Coin{
    public static void main(String[] args) {
        
    }
}
// 面试题 08.11. 硬币
class Solution {
    public static int waysToChange(int n) {
        final int MOD = 1000000007;
        int[] ways = new int[n+1];
        int[] coins = {25,10,5,1};
        for(int coin:coins){
            for(int i=coin;i<n+1;i++){
                ways[i] = (ways[i]+ways[i-coin])%MOD;
            }
        }
        return ways[n];
    }
}